package org.hot100_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode57 {


//    List<List<String>> res = new ArrayList<>();
//
//    public List<List<String>> solveNQueens(int n) {
//        char [][] chessboard = new char[n][n];
//        for (char [] temp:chessboard) {
//            Arrays.fill(temp,'.');
//        }
//        backtracking(chessboard,n,0);
//        return  res;
//    }
//    private void backtracking(char[][]chessboard,int n ,int row){
//        if (row==n){
//            res.add(arrayToList(chessboard));
//            return;
//        }
//
//        for (int col=0; col < n; col++) {
//            if (isValid(chessboard,n,row,col)){
//                chessboard[row][col]='Q';
//                backtracking(chessboard,n,row+1);
//                chessboard[row][col]='.';
//            }
//        }
//    }
//
//    private List arrayToList(char[][]chessboard){
//        List<String> list = new ArrayList<>();
//        for (char [] temp:chessboard) {
//            list.add(String.copyValueOf(temp));
//        }
//        return list;
//    }
//
//    private boolean isValid(char[][]chessboard,int n ,int row,int col){
//        //每一列
//        for (int i = 0; i < row; i++) {
//            if (chessboard[i][col]=='Q'){
//                return false;
//            }
//        }
//
//        //45
//        for (int i = row-1, j =col-1; i>=0 && j>=0; i--,j--) {
//            if (chessboard[i][j]=='Q'){
//                return false;
//            }
//        }
//
//
//        //135
//        for (int i = row-1, j =col+1; i>=0 && j<n; i--,j++) {
//            if (chessboard[i][j]=='Q'){
//                return false;
//            }
//        }
//
//        return true;
//    }

    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char [][] chessboard = new char[n][n];
        Arrays.fill(chessboard,'.');
        return res;
    }

    private void backtracking(char[][] chessboard,int n,int start){

        if (start==n){
            res.add(arrToList(chessboard));
            return;
        }

        for (int j = 0; j < n; j++) {
            if (isValid(chessboard,start,j)){
                chessboard[start][j]='Q';
                backtracking(chessboard,n,start+1);
                chessboard[start][j]='.';
            }
        }


    }

    private boolean isValid(char[][] chessboard,int row,int col){
        int n  = chessboard.length;
        //45度
        for (int i = row-1,j =col-1; i >=0 && j>=0; i--,j--) {
          if (chessboard[i][j]=='Q'){
              return false;
          }
        }

        //135度
        for (int i = row-1,j =col-1; i >=0 && j<n; i--,j++) {
            if (chessboard[i][j]=='Q'){
                return false;
            }
        }
        //上下

        for (int i = row-1; i >=0; i++) {
           if (chessboard[i][col]=='Q'){
               return false;
           }
        }
        return true;
    }

    private List arrToList(char [][] array){
        List<String> list =new ArrayList();

//        for (String [] item:array) {
//            list.add(String.copyValueOf(item));
//        }

        return list;
    }


    public static void main(String[] args) {
        String [] test = new String[3];
        test[0]="zhang";
        test[1]="zhen";
        test[2]="abc";

//
//        for (String str :test){
//            System.out.println(str);
//        }
    }



}
